package l.l.w.CodingInterviews;

/**
 * Created by llw on 2018/4/3/0003.
 */
public class 两个链表的第一个公共结点 {
    public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
        ListNode cur1 = pHead1,cur2 = pHead2;
        while(cur1 != cur2){
            cur1 = cur1.next;
            cur1 = cur1== null ? pHead2 : cur1;
            cur2 = cur2.next == null ? pHead1 : cur2.next;
        }
        return cur1;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1=pHead1,cur2 = pHead2;
        int len1 = 0, len2 = 0;
        while(cur1 != null){
            cur1 = cur1.next;
            len1++;
        }
        while(cur2 != null){
            cur2 = cur2.next;
            len2++;
        }
        if(len1 < len2){
            int temp = len1;
            len1 = len2;
            len2 = temp;
            cur1 = pHead2;
            cur2 = pHead1;
        }else{
            cur1 = pHead1;
            cur2 = pHead2;
        }
        for(int i = 0; i < (len1 - len2); ++i){
            cur1 = cur1.next;
        }
        while(cur1 != null){
            if(cur1 == cur2) return cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode h1 = new ListNode(1);
        ListNode h3 = h1.add(2).add(3);
        ListNode h2 = new ListNode(4);
        h2.add(5);
        ListNode h6 = new ListNode(6);
        ListNode h7 = new ListNode(7);
        h6.next = h7;
        h3.next = h6;
        h2.next.next = h6;


        ListNode result = new 两个链表的第一个公共结点().FindFirstCommonNode1(h1, h2);
        System.out.println(result.val);
    }
}
